/**
 * All rights Reserved, Designed By 溪云阁
 * Copyright:    Copyright(C) 2016-2020
 */

package com.algorithm;

import java.util.Arrays;

/**
 * 希尔算法
 * @author：溪云阁
 * @date：2020年5月3日
 */

public class ShellAlgorithm {

    /**
     * 希尔排序
     * @author 溪云阁
     * @param arrays void
     * 希尔排序是插入排序的改进版，
     * 它将数组按照约定的数量分成N列，对每一列执行插入排序，接着缩小步长
     * 不断重复这过程，最后整个表就只有一列了
     */
    public static void shellSort(int[] arrays) {
        if (arrays == null || arrays.length <= 1) {
            return;
        } else {
            // 增量
            int incrementNum = arrays.length / 2;
            while (incrementNum >= 1) {
                for (int i = 0; i < arrays.length; i++) {
                    // 进行插入排序
                    for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
                        if (arrays[j] > arrays[j + incrementNum]) {
                            final int temple = arrays[j];
                            arrays[j] = arrays[j + incrementNum];
                            arrays[j + incrementNum] = temple;
                        }
                    }
                }
                // 设置新的增量
                incrementNum = incrementNum / 2;
            }
        }
    }

    public static void main(String[] args) {
        final int[] arr = { 2, 3, 5, 1, 23, 6, 78, 34, 23, 4, 5, 78, 34, 65, 32, 65, 76, 32, 76, 9 };
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

}
